// m
// 给定一个n*n大小的二维矩阵matrix，将二位矩阵matrix顺时针旋转90
// 说明，不使用额外的数组空间

// 思路1： 原地旋转
// 观察每个位置上的点最初位置和最终位置有什么规律
// 矩阵中第i行，j列的点，出现在倒数第i列第j行

// 复杂度分析
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
/**
 * i，j
   j , n - i - 1
   n - i - 1, n - j - 1
   n -j - 1, i 

[  [i, j],  [n -j - 1, i], [n-i-1, n-j- 1], [j, n-i-1]]  = [[n-j-1, i], [n-i-1, n-j- 1], [j, n-i-1], [i, j]]
 * 
 */
function rotate(matrix) {
    let n = matrix.length
    for (let i = 0; i < Math.floor(n / 2); i++) {
        for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
            [matrix[i][j], matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1]] = [matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1], matrix[i][j]]
        }
    }
}

let matrix1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
let matrix2 = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
rotate(matrix1)
console.log(matrix1);

rotate(matrix2)
console.log(matrix2);


// 思路2，原地翻转
// 原矩阵可以通过一次 水平翻转 + 主对角线翻转 得到旋转后的二维矩阵

// 复杂度分析
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)

function rotate2(matrix) {
    let n = matrix.length

    for (let i = 0; i < Math.floor(n / 2); i++) {
        for (let j = 0; j < n; j++) {
            [matrix[i][j], matrix[n - i - 1][j]] = [matrix[n - i - 1][j], matrix[i][j]]
        }
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]
        }
    }

}

let matrix3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
let matrix4 = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
rotate2(matrix3)
console.log(matrix3);

rotate2(matrix4)
console.log(matrix4);